1. Field of the Invention
The present invention is related to the field of computer systems. Specifically, the present invention relates to optimizing cost-based heuristic instruction scheduling for a pipelined processor.
2. Art Background
In the co-pending U.S. patent application Ser. No. 07/661,674, filed on Feb. 27, 1991, invented by the inventors of the present invention, G. Tarsy and M. Woodard, assigned to the assignee of the present Application, Sun Microsystems Inc., entitled Method and Apparatus for Cost-based Heuristic Instruction Scheduling, a method and apparatus for cost-based heuristic instruction scheduling for a pipelined processor is disclosed which has particular application to compile time instruction scheduling after code generation.
The method for cost-based heuristic instruction scheduling for a pipelined processor of the co-pending Application comprises the steps of building an instruction dependency graph for a block of instructions to be scheduled, building a free instruction list for the instructions based on the instruction dependency graph, and scheduling one of the free instructions based on the lowest total cost of the free instructions. The total cost for each of the free instructions is computed based on the weighted sum of a plurality of cost heuristics. Additionally, the free instruction list is refreshed after a free instruction is scheduled and another one of the free instructions from the refreshed list is scheduled. The refreshing and scheduling is repeated until the instructions of the instruction block are all scheduled.
The apparatus for cost-based heuristics instruction scheduling for a pipelined processor of the co-pending Application comprises a dependency graph building procedure for building an instruction dependency graph, a list building procedure for building and refreshing a free instruction list, and a scheduling procedure for scheduling one of the free instructions. Additionally, the preferred embodiment of the apparatus of the co-pending Application further comprises a processor model for modeling some of the cost heuristics.
The cost heuristics of the method and apparatus of the co-pending Application comprise a resource dependency cost, a data dependency cost, a dependency wait cost, a dependent cycle cost, a floating point ratio cost, a store ratio cost, and a floating point queue cost. The weights of the cost heuristics represent the relative importance of the cost heuristics for a particular pipelined processor.
The salient characteristics of pipelined processors vary significantly from one processor to the other, for example, single cycle integer load/use penalty and floating point load/use penalty. Empirical evidence has shown that weights customized for a particular pipelined processor substantially improve the effectiveness of the method and apparatus for cost-based heuristic instruction scheduling described in the co-pending Application.
As will be described, the present invention further improves the effectiveness of the method and apparatus of the co-pending Application, and provides a complementary method and apparatus for optimizing cost-based heuristic instruction scheduling for a pipelined processor.